package sliding_window

import "math"

/*
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。

示例 1：
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
示例 2：

输入：nums = [5], k = 1
输出：5.00000

*/

//此题解，会超出时间限制
func findMaxAverage(nums []int, k int) float64 {
	left, right := 0, 0
	var result float64 = math.MinInt

	for right < len(nums) {
		//扩大窗口
		right++

		//固定一个长度为k的窗口,进行收缩
		for right-left >= k {
			//窗口收缩完成，进行计算平均值
			if right-left == k {
				avg := average(nums[left:right])
				if avg > result {
					result = avg
				}
			}

			//搜索窗口
			left++
		}

	}
	return result
}

//滑动窗口累积的过程是：
//sum[i]=sum[i-1]-nums[i-k]+nums[i] //有移除的就有移入的
//可以看成是维护一个长度为k的滑动窗口，当滑动窗口从下标范围[i-k,i-1]移动到下标范围[i-k+1,i]时，nums[i-k]从窗口中移出，nums[i]进入窗口内
func findMaxAverage1(nums []int, k int) float64 {
	sum := 0
	//初始化长度为k的和
	for _, v := range nums[:k] {
		sum += v
	}
	maxSum := sum
	for i := k; i < len(nums); i++ {
		sum = sum - nums[i-k] + nums[i]
		maxSum = max(maxSum, sum)
	}
	return float64(maxSum) / float64(k)
}

func average(xs []int) (avg float64) {
	sum := 0.0
	switch len(xs) {
	case 0:
		avg = 0
	default:
		for _, v := range xs {
			sum += float64(v)
		}
		avg = sum / float64(len(xs))
	}
	return
}
